package com.github.hgkmail.hello.leetcode101.collection.stack;

import java.util.Arrays;
import java.util.Stack;

//单调栈：维护一个递增或递减的栈，如果遇到违反的元素就弹出
//这道题维护一个递减的栈，[温度变小就压入]，遇到温度变大就弹出，栈内存坐标而不直接存温度
public class LC739DailyTemperatures {
    public int[] dailyTemperatures(int[] temperatures) {
        int len = temperatures.length;
        if (len<=0) {
            return new int[]{};
        }
        int[] res = new int[len];
        //递减栈，存下标
        Stack<Integer> indexStack = new Stack<>();
        for (int i = 0; i < len; i++) {
            int currTemp = temperatures[i];
            if (indexStack.isEmpty()) {
                indexStack.push(i);
                continue;
            }
            int topIndex = indexStack.peek();
            int topTemp = temperatures[topIndex];
            if (currTemp<=topTemp) {
                //递减，存入
                indexStack.push(i);
                continue;
            }
            //递增，弹出
            while (!indexStack.isEmpty() && currTemp>temperatures[indexStack.peek()]) {
                topIndex = indexStack.pop();
                res[topIndex] = i-topIndex;
            }
            indexStack.push(i);
        }
        while (!indexStack.isEmpty()) {
            res[indexStack.pop()]=0;
        }

        return res;
    }

    public static void main(String[] args) {
        System.out.println(Arrays.toString(new LC739DailyTemperatures().dailyTemperatures(new int[]{73,74,75,71,69,72,76,73})));
    }
}
